package DataStructures;

import java.util.Iterator;

public class MyArrayList<T> implements Iterable<T> {
	private static final int DEFAULT_CAPACITY = 10;
	private int theSize;
	private int modCount;
	private T [] theItems;
	
	public MyArrayList() {
		clear();
	}

	public void clear() {
		theSize = 0;
		ensureCapacity(DEFAULT_CAPACITY);
		modCount++;
	}
	public int size() {
		return theSize;
	}
	public boolean isEmpty() {
		return size() == 0;
	}
	public void trimToSize() {
		ensureCapacity(size());
	}
	public T get(int idx) {
		return theItems[idx];
	} 
	public T set(int idx, T newVal) {
		T old = theItems[idx];
		theItems[idx] = newVal;
		return old;
	}
	public void ensureCapacity(int newCapacity) {
		if(newCapacity < size())
			return ;
		T [] old = theItems;
		theItems = (T []) new Object[newCapacity];
		for(int i = 0; i < size(); i++)
			theItems[i] = old[i];
	}
	public boolean add(T x) {
		add(size(), x);
		return true;
	}
	public void add(int idx, T x) {
		if(theItems.length == size())
			ensureCapacity(size() * 2 + 1);
		for(int i = size(); i > idx; i--)
			theItems[i] = theItems[i - 1];
		theItems[idx] = x;
		
		theSize++;
		modCount++;
	}
	public T remove(int idx) {
		T removedItem = theItems[idx];
		for(int i = idx; i < size() - 1; i++)
			theItems[idx] = theItems[idx + 1];
		
		theSize--;
		modCount++;
		return removedItem;
	}
	
	//exercise 3.9    O(n)
	public void addAll(Iterable<? extends T> items) {
		Iterator<? extends T> itr = items.iterator();
		
		while(itr.hasNext())
			add(itr.next());
		modCount++;
	}
	
	public Iterator<T> iterator() {
		return new ArrayListIterator();
	}
	private class ArrayListIterator implements Iterator<T> {
		private int current = 0;
		private int expectedModCount = modCount;
		private boolean okToRemove = false;
		
		public boolean hasNext() {
			return current < size();
		}
		
		public T next() {
			if(modCount != expectedModCount)
				throw new java.util.ConcurrentModificationException();
			if(!hasNext())
				throw new java.util.NoSuchElementException();
			okToRemove = true;
			return theItems[current ++];
		}
		
		public void remove() {
			if(modCount != expectedModCount)
				throw new java.util.ConcurrentModificationException();
			if(!okToRemove)
				throw new IllegalStateException();
			MyArrayList.this.remove(--current);
			okToRemove = false;
			expectedModCount++;
		}
	}
	//3.16
	public Iterator<T> reverseIterator() {
		return new ArrayListReverseIterator();
	}
	
	private class ArrayListReverseIterator implements Iterator<T> {
		private int current = size() - 1;
		
		public boolean hasNext() {
			return current >= 0;
		}
		
		public T next() {
			if(!hasNext())
				throw new java.util.NoSuchElementException();
			return theItems[current--];
		}
		
		public void remove() {
			MyArrayList.this.remove(++current);
			current--;
		}
	}
}
